package com.wf.classRoomTest;

import java.util.Arrays;

/**
 * @author mpk
 * @since 2024/6/6 09:47:05
 */
public class HeapSortDemo {
    public static void main(String[] args) {

        int[] arr = {7, 14, 2, 1, 20, 17, 8, 4, 5, 9};

        heapSort(arr);

        System.out.println(Arrays.toString(arr));

    }


    /**
     * @param arr 要调整的数组
     */

    public static void heapSort(int[] arr) {

        for (int i = arr.length / 2 - 1; i >= 0; i--) {

            heapIfy(arr, arr.length, i);
        }
        for (int i = arr.length - 1; i >= 0; i--) {

            swap(arr, 0, i);

            heapIfy(arr, i, 0);

        }

    }

    /**
     * @param arr 要调整的数组
     * @param n   对多少个元素进行调整,
     * @param i   需要调整节点的下标 表示非叶子节点在数组中的索引。即 i = n / 2 - 1
     */

    public static void heapIfy(int arr[], int n, int i) {

        int largest = i;
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        if (leftChild < n && arr[largest] < arr[leftChild]) {
            largest = leftChild;
        }
        if (rightChild < n && arr[largest] < arr[rightChild]) {

            largest = rightChild;
        }

        if (largest != i) {
            swap(arr, largest, i);

            heapIfy(arr, n, largest);
        }


    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;

    }


}
